洛谷题解 P3958 【奶酪】

首先这道题要用到以下知识:

并查集、圆与圆的位置关系(可推广到球与球)、空间两点坐标公式

空间两点坐标公式体面给了,这里不讲。

先讲圆与圆的位置关系判定:

如图,从上到下,从左到右依次是:外离,外切,相交,内切,内含

设两圆圆心距离为$d(d>0)$,半径为$r_1$、$r_2$

则有以下关系:

外离:$d>r_1+r_2$

外切:$d=r_1+r_2$

相交:$|r_1-r_2|<d<r_1+r_2$

内切:$d=|r_1-r_2|$

内含:$d<|r_1-r_2|$

此结论可以直接推广至球与球的位置关系。

对于本题,我们只需要考虑外离、相切、相交三种情况,内切和内含可略去(没有意义)。

题中默认$z$轴正方向向上,$x$轴、$y$轴随意(不影响)

我的思路是:

每个球各化为一点,

顶层底层各是一点,

若相切相交即为合并,

最后再验顶底同祖宗。

对于此题,除了用上外离、外切、相交的判定外,还有:

若$z-r<=0$,则该球与底部相交/相切。

若$z+r>=h$,则该球与顶部相交/相切。

贴代码,附解析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
定义底层节点编号为0,顶层节点编号为n+1
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int n,h,r,fa[1010],T;//fa存父节点
int x[1010],y[1010],z[1010];//你懂得

double dis(double xa,double ya,double za,double xb,double yb,double zb)//套公式
{
return (double)(sqrt((double)(xa-xb)*(xa-xb)+(double)(ya-yb)*(ya-yb)+(double)(za-zb)*(za-zb)));
}

int find(int s)//注意用了路径压缩
{
int k=s,t;
while(k!=fa[k])
{
k=fa[k];
}
while(s!=fa[s])
{
t=s;
s=fa[s];
fa[t]=k;
}
return k;
}

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&h,&r);
for(int a=0;a<=n+1;a++)//注意每次要初始化父节点为自己
{
fa[a]=a;
}
for(int a=1;a<=n;a++)
{
scanf("%d%d%d",&x[a],&y[a],&z[a]);
if(z[a]-r<=0)//底层合并
{
if(find(a)!=find(0))
{
fa[find(a)]=find(0);
}
}
if(z[a]+r>=h)//顶层合并
{
if(find(a)!=find(n+1))
{
fa[find(a)]=find(n+1);
}
}
for(int b=1;b<a;b++)//洞间合并
{
if(2*r>=dis(x[a],y[a],z[a],x[b],y[b],z[b]))
{
if(find(a)!=find(b))
{
fa[find(a)]=find(b);
}
}
}
}
if(find(0)==find(n+1))//验顶层底层是否连通
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return 0;
}

题目详见:https://www.luogu.com.cn/problem/P3958